package simple.stack;

import java.util.Stack;

/**
 * <a href="https://leetcode-cn.com/problems/valid-parentheses">20. 有效的括号</a>
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 *   左括号必须用相同类型的右括号闭合。
 *   括号必须以正确的顺序闭合。
 * 示例 1：
 *   输入：s = "()"
 *   输出：true
 * 示例 2：
 *   输入：s = "()[]{}"
 *   输出：true
 * 示例 3：
 *   输入：s = "(]"
 *   输出：false
 * 示例 4：
 *   输入：s = "([)]"
 *   输出：false
 * 示例 5：
 *   输入：s = "{[]}"
 *   输出：true
 * 提示：
 *   1 <= s.length <= 104
 *   s 仅由括号 '()[]{}' 组成
 * 解题思路：利用栈的后进先出的特性
 *   1.根据题意可知，有效括号的前提是字符串长度为偶数，若长度为奇数，则直接返回false，这里用按位与1运算可快速判断长度的奇偶
 *   2.遍历字符串中的每个字符
 *   3.若字符为起始括号，则将对应的结束括号入栈（栈中只对结束括号进行操作，当字符为结束括号时方便出栈）
 *   4.若为结束括号，则要出栈，并且判断出栈的结束括号与当前结束括号是否相同（从左往右，首个结束括号的左边那个一定是对应的起始括号），不相同则返回false
 *   5.另外，出栈时如果栈里没有元素，则会异常，因此在出栈前判断栈是否为空栈，为空表示当前结束括号的左边没有对应的起始括号，直接返回false
 *   6.遍历完后，若栈里为空，表示所有的结束括号都与起始括号一一对应消除了，可以认定为该字符串为有效括号，否则为无效括号，因此直接返回栈大小是否等于0
 * @author 刘学松
 * @date 2021-03-14 22:06
 */
public class 有效的括号 {
    public static void main(String[] args) {
        String s = "([)]";
        System.out.println(isValid(s));
    }

    public static boolean isValid(String s) {
        if (0 != (s.length() & 1)) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (char character : s.toCharArray()) {
            if (character == '(') {
                stack.push(')');
            } else if (character == '[') {
                stack.push(']');
            } else if (character == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || character != stack.pop()) {
                return false;
            }
        }
        return stack.isEmpty();
    }

    public boolean isValid1(String s1) {
        int x = 0, n = s1.length();
        if (0 != (n & 1)) {
            return false;
        }
        byte s[] = s1.getBytes();
        for (int i = 0, j = 0; i < n; ++i) {
            if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
                --x;
                if (0 == j--) {
                    return false;
                }
                if (s[j] + 2 != s[i] && s[j] + 1 != s[i]) {
                    return false;
                }
            } else {
                s[j++] = s[i];
                ++x;
            }
        }
        return x == 0;
    }
}
